package leetcode.pre150;


/**
 * 拓展。可能存在重复元素
 * 旋转数组找最小值。
 * [1,2,3,4,5,6] -> [4,5,6,1,2,3]
 * <p>
 * 不存在重复元素的见
 * {@link Code153_FindMin1}
 * <p>
 * 旋转数组其他问题见
 * {@link leetcode.a_总结分布.Code13_旋转数组问题}
 *
 * @date 2020/3/24 16:24
 */
public class Code154_FindMin2 {

    public static int findMin(int[] arr) {
        if (arr == null || arr.length == 0) throw new RuntimeException("illegal");
        if (arr.length == 1) return arr[0];
        //如果没有旋转
        if (arr[0] < arr[arr.length - 1]) return arr[0];
        //二分查找
        int l = 0; //l只会向着左侧数组的最大值靠近，但是不会超出
        int r = arr.length - 1;//r只会想着右侧数组的最小值靠近，但不会超出
        while (l < r) {
            int mid = (r + l) >> 1;
            if (r - l == 1) {
                return arr[r];
            }
            //[0,1,1,1,1] -> [1,0,1,1,1] 或[1,1,1,0,1]等.分不清，顺序查找
            if (arr[l] == arr[mid] && arr[l] == arr[r]) {
                return inOrder(arr, l, r);
            }
            //TODO,注意这里要加等号，不然{2,2,2,0,1}执行不了正确结果
            // 在左侧的数组中
            if (arr[l] <= arr[mid]) {
                l = mid;
            } else {//在右侧的数组中。
                r = mid;
            }
        }
        return -1;
    }

    private static int inOrder(int[] arr, int l, int r) {
        int min = arr[l++];
        while (l <= r) {
            min = Math.min(arr[l++], min);
        }
        return min;
    }

    public static void main(String[] args) {
        int[] arr1 = {2, 2, 2, 0, 1};
//        int[]arr2 = {1,1,1,0,1};
        System.out.println(findMin(arr1));
//        System.out.println(findMin(arr2));
    }
}
